package com.zephyr.wing.huawei.od.alg.alg100.e;

import java.util.*;
import java.util.stream.Collectors;

public class OrganizePlayingCards {

    /**
     *
     * 题目
     * 给定一组数字，表示扑克牌的牌面数字，忽略扑克牌的花色，请按如下规则对这一组扑克牌进行整理：
     * 步骤1. 对扑克牌进行分组，形成组合牌，规则如下：当牌面数字相同张数大于等于4时，组合牌为“炸弹”；
     *       3张相同牌面数字 + 2张相同牌面数字，且3张牌与2张牌不相同时，组合牌为“葫芦”；
     *       3张相同牌面数字，组合牌为“三张”； 2张相同牌面数字，组合牌为“对子”； 剩余没有相同的牌，则为“单张”；
     * 步骤2. 对上述组合牌进行由大到小排列，规则如下：不同类型组合牌之间由大到小排列规则：“炸弹” > “葫芦” > “三张” > “对子” > “单张”；
     *       相同类型组合牌之间，除“葫芦”外，按组合牌全部牌面数字加总由大到小排列；
     *       “葫芦”则先按3张相同牌面数字加总由大到小排列，3张相同牌面数字加总相同时，再按另外2张牌面数字加总由大到小排列；
     *       由于“葫芦”>“三张”，因此如果能形成更大的组合牌，也可以将“三张”拆分为2张和1张，其中的2张可以和其它“三张”重新组合成“葫芦”，剩下的1张为“单张”
     * 步骤3. 当存在多个可能组合方案时，按如下规则排序取最大的一个组合方案：依次对组合方案中的组合牌进行大小比较，规则同上；
     *       当组合方案A中的第n个组合牌大于组合方案B中的第n个组合牌时，组合方案A大于组合方案B；
     *
     * 输入描述
     * 第一行为空格分隔的N个正整数，每个整数取值范围[1,13]，N的取值范围[1,1000]
     *
     * 输出描述
     * 经重新排列后的扑克牌数字列表，每个数字以空格分隔
     *
     * 用例一：
     * 输入：
     * 1 3 3 3 2 1 5
     * 输出：
     * 3 3 3 1 1 5 2
     *
     * 用例二：
     * 输入：
     * 4 4 2 1 2 1 3 3 3 4
     * 输出：
     * 4 4 4 3 3 2 2 1 1 3
     *
     * 解题思路
     *
     * 题目要求对卡片按出现次数进行重新排列，排序规则如下：
     *
     * 出现次数为 4 的卡片：按卡片值降序排列。出现次数为 3 的卡片：按卡片值升序排列，并尽量与出现次数为 2 的卡片配对。出现次数为 2 的卡片：按卡片值升序排列。出现次数为 1 的卡片：按卡片值降序排列。关键步骤：统计每张卡片的出现次数：使用 Map<Integer, Integer> 来统计每个卡片的出现次数。分类：将卡片按出现次数分类为 1 次、2 次、3 次和 4 次。排序：按照题目要求，对每个分类的卡片进行排序：对 4 次出现的卡片按出现次数和卡片值降序排序。对 3 次和 2 次出现的卡片按升序排序。对 1 次出现的卡片按降序排序。拼接结果：根据排序后的卡片，将它们按顺序加入最终结果列表。在处理 3 次出现的卡片时，优先配对 2 次出现的卡片或单张卡片。
     *
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> numbers = new ArrayList<>();
        // 读取输入直到输入结束
        while (sc.hasNextInt()) {
            numbers.add(sc.nextInt());
        }
        // 输出处理后的卡片排列顺序
        System.out.println(processCards(numbers));
    }
    // 处理卡片排列的函数
    public static String processCards(List<Integer> numbers) {
        // Step 1: 统计每张卡片的出现次数
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : numbers) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        // Step 2: 将卡片按出现次数分组
        Set<Integer> singles = new HashSet<>();
        Set<Integer> pairs = new HashSet<>();
        Set<Integer> triples = new HashSet<>();
        Set<Integer> quads = new HashSet<>();
        // 遍历出现次数统计，分配到相应的集合中
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            if (freq == 1) {
                singles.add(num);  // 1次出现的卡片
            } else if (freq == 2) {
                pairs.add(num);    // 2次出现的卡片
            } else if (freq == 3) {
                triples.add(num);  // 3次出现的卡片
            } else {
                quads.add(num);    // 4次出现的卡片
            }
        }
        // Step 3: 创建一个结果列表，存放排序后的卡片
        List<Integer> result = new ArrayList<>();
        // 处理出现次数为4的卡片，按出现次数和卡片值降序排列
        List<Integer> quadsList = new ArrayList<>(quads);
        quadsList.sort((a, b) -> count.get(b) != count.get(a) ? count.get(b) - count.get(a) : b - a);
        for (int q : quadsList) {
            for (int i = 0; i < count.get(q); i++) {
                result.add(q);  // 将出现次数为4的卡片添加到结果中
            }
        }
        // Step 4: 处理出现次数为3的卡片，并尽量与2次的卡片配对
        List<Integer> triplesList = new ArrayList<>(triples);
        List<Integer> pairsList = new ArrayList<>(pairs);
        Collections.sort(triplesList);  // 对出现次数为3的卡片升序排序
        Collections.sort(pairsList);    // 对出现次数为2的卡片升序排序
        while (!triplesList.isEmpty()) {
            int t = triplesList.remove(triplesList.size() - 1);  // 从列表末尾取出3次的卡片
            result.add(t);  // 将3次的卡片添加到结果中
            result.add(t);  // 添加两次
            result.add(t);  // 添加三次
            // 判断是否能和二次的卡片配对，或者如果没有二次卡片则与单次卡片配对
            if (!triplesList.isEmpty() && (pairsList.isEmpty() || triplesList.get(triplesList.size() - 1) > pairsList.get(pairsList.size() - 1))) {
                int leftover = triplesList.remove(triplesList.size() - 1);  // 从3次卡片中移除一个
                singles.add(leftover);  // 将剩余卡片的一个值放入单张卡片的集合中
                result.add(leftover);   // 添加剩余的单张卡片
                result.add(leftover);   // 再添加一次
            } else if (!pairsList.isEmpty()) {
                int p = pairsList.remove(pairsList.size() - 1);  // 从二次卡片中取出一个卡片
                result.add(p);  // 添加到结果中
                result.add(p);  // 再添加一次
            }
        }
        // Step 5: 处理出现次数为2的卡片
        while (!pairsList.isEmpty()) {
            int p = pairsList.remove(pairsList.size() - 1);  // 从二次卡片中取出一个
            result.add(p);  // 添加到结果中
            result.add(p);  // 再添加一次
        }
        // Step 6: 处理出现次数为1的卡片，按降序排列
        List<Integer> singlesList = new ArrayList<>(singles);
        singlesList.sort(Collections.reverseOrder());  // 将单张卡片按降序排列
        result.addAll(singlesList);  // 添加到结果中
        // 返回处理后的结果，使用空格连接
        return result.stream().map(String::valueOf).collect(Collectors.joining(" "));
    }
}
